Problem :

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1 :

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2 :

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 ste

核心思維 :

1. 設定變量cur和pre，以儲存當前和前一階段的結果
2. 循環n次，計算從底部到頂部的方式數量

• cur的變量更新，當前階段的方式數 = 前一階段的方式數 + 當前階段的方式數
• 更新pre為當前階段的值，以進行下一次迴圈

3. 回傳最終爬樓梯方式的數量

程式碼 :

class Solution {
public:
    int climbStairs(int n) {
        //設定變量cur和pre，以儲存當前和前一階段的結果
        int cur = 1, pre = 0;
        //循環n次，計算從底部到頂部的方式數量
        for(int i = 0; i < n; i++){
            cur = pre + cur;
            //cur的變量更新，當前階段的方式數 = 前一階段的方式數 + 當前階段的方式數
            pre = cur - pre;
            //更新pre為當前階段的值，以進行下一次迴圈
        }
        //回傳最終爬樓梯方式的數量
        return cur;
    } 
};

結論 :

這題的目標是計算樓梯n階共有幾種爬樓梯的方式，從變量初始化開始，再來進行迴圈並計算爬樓梯種類的方式數，最後返回結果，使用動態規劃的思路，時間複雜度是O(n)，空間複雜度是O(1)，這題利用動態規劃儲存過程結果的特性，逐一將每一次計算出的爬樓梯方式數量相加，最後得到爬樓梯方式的總數。